package LearnAlgorithm.d_标准查找算法and标准排序算法;

import java.util.HashMap;

public class b5e快速排序by双向扫描分区方式plus三分法plus绝对中值优化plus小数组插入排序优化 {
	public static void main(String[] args) {
		int[] arr = new int[] {6,8,7,9,5,4,3,4,4,6,6,6,8,7,9,5,4,3,4,4,6,6};
		long before = System.currentTimeMillis();
		quickSortThree(arr, 0, arr.length - 1);
		util.Util.duration(before);
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
	//O(NlogN)
	public static void quickSortThree(int[] arr, int p, int r) {
		if (p < r) {
			if (r - p + 1 <= 8) {
				insertSort(arr, p, r);
			} else {
				int[] q = partitionThree(arr, p, r);
				quickSortThree(arr, p, q[0] - 1);
				quickSortThree(arr, q[1] + 1, r);
			}
		}
	}
	
	//三分法不适合自己想的那一种“中值不换位置”的算法思想
	//因为等于中值的相同值是要看做“一块区域”
	//在数组整体有限的“长度”下，定死一块区域很傻
	//这块不灵活的区域会出很多问题：
	//假设相等值都在mid左侧，如果mid后面的值都小于piovet，需要被交换到前面去
	//然而前面有很多的相等值占据了位置，这不就出大问题了么
	public static int[] partitionThree(int[] arr, int p, int r) {
		int e = p + 1;
		int sp = p + 1;
		int bigger = r;
		int midIndex = getMedian(arr, p, r);
		swap(arr, p, midIndex);
		int piovet = arr[p];
		int[] equalNumber = new int[2];
		while (sp <= bigger) {
			while (sp <= bigger && arr[sp] <= piovet) {
				if (arr[sp] < piovet && sp == e) {
					sp++;
					e++;
				} else if (arr[sp] < piovet && sp != e) {
					swap(arr, e, sp);
					sp++;
					e++;
				} else {
					sp++;
				}
			}
			while (sp <= bigger && arr[bigger] > piovet) {
				bigger--;
			}
			if (sp < bigger) {
				swap(arr, sp, bigger);
			}
		}
		swap(arr, p, e - 1);
		equalNumber[0] = e - 1;
		equalNumber[1] = bigger;
		return equalNumber;
	}
	
	public static int getMedian(int[] arr, int p, int r) {
		int size = r - p + 1;
		int groupSize = (size % 5 == 0) ? (size / 5) : ((size / 5) + 1);
		int indexOfMedians = 0;
		int[] medians = new int[groupSize];
		HashMap<Integer, Integer> medainsOfValueAndIndex = new HashMap<Integer, Integer>();
		for (int i = 0; i < groupSize; i++) {
			if (i == groupSize - 1) {
				insertSort(arr, p + (i * 5), r);
				medians[indexOfMedians++] = arr[(p + (i * 5) + r) >>> 1];
				medainsOfValueAndIndex.put(arr[(p + (i * 5) + r) >>> 1], (p + (i * 5) + r) >>> 1);
			} else {
				insertSort(arr, p + (i * 5), p + (i * 5) + 4);
				medians[indexOfMedians++] = arr[p + (i * 5) + 2];
				medainsOfValueAndIndex.put(arr[p + (i * 5) + 2], p + (i * 5) + 2);
			}
		}
		insertSort(medians, 0, groupSize - 1);
		return medainsOfValueAndIndex.get(medians[(groupSize - 1) >>> 1]);
	}
	
	public static void insertSort(int[] arr, int p, int r) {
		int before_i = 0;
		int value_i = 0;
		for (int i = p + 1; i <= r; i++) {
			before_i = i - 1;
			value_i = arr[i];
			while (before_i > p - 1 && arr[before_i] > value_i) {
				arr[before_i + 1] = arr[before_i--];
			}
			arr[before_i + 1] = value_i;
		}
	}
	
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}
